/**
 * Java implementation of a Splay Tree of type T.
 * 
 * @author Jonathan E. Landrum <me@jonlandrum.com>
 * @since 2016-01-04
 */

package com.jonlandrum.selfbalancingtree.splaytree;

import com.jonlandrum.selfbalancingtree.Node;
import com.jonlandrum.selfbalancingtree.SelfBalancingTree;

public class SplayTree<T extends Comparable<T>> extends SelfBalancingTree<T> {
    /*
     * Constructors
     */
    public SplayTree() {
        super();
    }
    
    public SplayTree(T d) {
        super(d);
    }
    
    public SplayTree(Node<T> n) {
        super(n);
    }
    
    /*
     * Operations
     */
    @Override
    public Node<T> addElement(T d) {
        return this.addElement(new Node<T>(d));
    }
    
    @Override
    public Node<T> addElement(Node<T> n) {
        Node<T> result = super.addElement(n);
        if (!result.isEmpty() && !result.isRoot()) {
            this.splay(result);
        }
        return result;
    }
    
    @Override
    public Node<T> findElement(T d) {
        return this.findElement(new Node<T>(d));
    }
    
    @Override
    public Node<T> findElement(Node<T> n) {
        Node<T> result = super.findElement(n);
        if (!result.isEmpty() && !result.isRoot()) {
            this.splay(result);
        }
        return result;
    }
    
    @Override
    public Node<T> removeElement(T d) {
        return this.removeElement(new Node<T>(d));
    }
    
    @Override
    public Node<T> removeElement(Node<T> n) {
        Node<T> result = super.removeElement(n);
        if (!result.isEmpty() && !result.isRoot()) {
            this.splay(result);
        }
        return result;
    }
    
    protected void splay(Node<T> n) {
        while (!n.isRoot()) {
            if (n.isLeftChild()) {
                this.rotateRight(n.getParent());
            } else {
                this.rotateLeft(n.getParent());
            }
        }
    }
}